package leetcode_1_20;

public class maxArea_11 {
    /**
     * 最大容器
     * 逻辑最简单的双层循环遍历
     * 时间复杂度 o(n²)，超时了
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        int maxArea=0;
        for(int i=0;i<height.length;i++){
            for(int j=0;j<height.length;j++){
                if(height[i]<height[j]){
                    int area=height[i]*(j-i);
                    maxArea=area>maxArea?area:maxArea;
                }else {
                    int area=height[j]*(j-i);
                    maxArea=area>maxArea?area:maxArea;
                }
            }
        }
        return maxArea;
    }

    /**
     * 尝试新方法
     * 开始两个指针一个指向开头一个指向结尾，
     * 此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，
     * 在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。
     * 能够发现不管是左指针向右移动一位，还是右指针向左移动一位，
     * 容器的底都是一样的，都比原来减少了 1。
     * 这种情况下想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，
     * 所以我们选择指针所指的高较小的那个指针进行移动，
     * 这样就保留了容器较高的那条边，放弃了较小那条边，以获得有更高的边的机会。
     *
     * 没有到极限速度
     * @param height
     * @return
     */
    public static int maxArea2(int[] height) {
        int maxArea=0;
        int beginIndex=0, endIndex=height.length-1;   //头尾指针
        while(beginIndex < endIndex){
            int area=(endIndex-beginIndex)*(Math.min(height[beginIndex], height[endIndex]));
            maxArea= Math.max(area, maxArea);
            if(height[beginIndex]>height[endIndex])
                endIndex--;           //同理
            else
                beginIndex++ ;    // 说明 height[beginIndex] 与右边的任意线段都无法组成一个比 area 更大的面积
        }
        return maxArea;
    }

    /**
     * 在2的基础上引入快速跳过
     * 速度1ms
     * @param height
     * @return
     */
    public static int maxArea3(int[] height) {
        int l = 0, r = height.length - 1;
        int maxArea = 0;
        while (l < r) {
            int area = (r - l) * Math.min(height[l], height[r]);
            int minH = Math.min(height[l], height[r]);
            maxArea = Math.max(maxArea, area);
            // 快速跳过这步可太妙了
            while (height[l] <= minH && l < r) {
                //改为循环判断而不是简单的条件判断，直接去掉大量无效的线段，减少大量循环
                // 因为底在减小，如果左边向右判断，下一个线段长度比现有的左右边框高度都低
                // 直接跳过这些线段的一系列判断
                l++;
            }
            while (height[r] <= minH && l < r) {
                //同理
                r--;
            }
        }
        return maxArea;
    }

}
